题目链接:https://www.acwing.com/problem/content/description/200/
题目大意:对于任何的正整数x,定义的约数个数。若对于任意的都有则称为反素数。现给定一个整数,求不超过N的最大的反素数是多少。
分析
首先的范围非常大,想要筛质数或者筛约数的方法肯定都做不了,顶多就对某个数筛一次,因此题目肯定有什么隐含的能够降低答案查找范围的条件没有挖掘出来。
性质1:中最大的反素数,就是范围内约数最多且最大的数。
证明:若是反素数,则需要满足:
性质2:中任何数的不同的质因子都不会超过10个,且所有质因子指数的总和不超过30
证明:最小的个质因子乘起来就已经超范围了,最小的质因子也会超范围。
至此我们已经把范围缩小到所求的质因子不超过10个,且指数控制在了一个有限的范围内,但这些条件还不足以去搜索,因为根本没法筛这么大范围的素数,肯定不行,还需要想办法缩小枚举的数的范围,和指数的范围。
性质3:最终答案的质因子只包括最小的前十个质因子,且指数呈下降趋势。
也就是说质因子只有这些数,且他们的指数
证明:假设有一个质因子,则原来的答案中一定存在一个满足,且不整除,但是我们可以构造出一个,由于约数的个数仅与指数有关,而新构造出来的显然又小于原来的答案,故不应该是一个反素数,矛盾。
其次,假设里的两个质因子分别是和,且。
如果我们把指数交换,同样可以构造出一个新的答案满足约数个数一致,但新的答案更大。因此我们可以构造出一个比原来答案更大的反素数,因此矛盾。
综上所述,我们可以做一个DFS搜索确定前十个数的指数和约数的个数,并更新答案。